package DataStructure.heap;

public class Heap<T extends Comparable<T>> {
    //存储堆中元素
    private T[] items;
    //记录元素个数
    private int N;

    //构造方法
    public Heap(int capacity){
        this.items=(T[])new Comparable[capacity+1];
        this.N=0;
    }

    //判断索引i处的值是否小于j
    public boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }

    //交换i和j处的元素
    public void exch(int i,int j){
        T temp=items[i];
        items[i]=items[j];
        items[j]=temp;
    }

    //往堆中插入一个元素
    public void insert(T t){
        items[++N]=t;//放弃0索引，不存储数据，数据从1处开始
        swim(N);
    }

    //使用上浮算法，是索引k处的值在堆中处于一个正确的位置
    public void swim(int k){
        //通过循环比较当前节点和父节点的值
        while (k>1){
            if(less(k/2,k)){
                exch(k/2,k);
            }
            k=k/2;
        }
    }

    //删除堆中最大元素并返回
    public T delMax(){
        T max=items[1];
        //交换1处的元素和索引最大处的元素，让最右侧的元素变为临时根节点
        exch(1,N);
        //把最大索引处的元素删除
        items[N]=null;
        //元素个数减1
        N--;
        //让堆重新有序
        sink(1);
        return max;
    }

    //使用下沉算法，使索引k处的元素处于一个正确的位置
    public void sink(int k){
        //通过循环不断对比当前k节点和（其左子节点2k以及右子节点2k+1处的）较大值的元素大小，如果当前节点小，则需要交换位置
        while (2*k<=N){
            //获取当前节点的子节点中的较大值
            int max;
            if(2*k+1<=N){
                if(less(2*k,2*k+1)){
                    max=2*k+1;
                }else {
                    max=2*k;
                }
            }else {
                max=2*k;
            }
            //比较当前节点和较大节点的值
            if(!less(k,max)){
                break;
            }
            //交换k和max的值
            exch(k,max);

            //变换k的值
            k=max;
        }

    }
}
